#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector> 
using namespace std;
typedef long long LL;
const LL MOD=2147493647ll;
class Martrix{
//	LL p[100];
	vector<LL> p;
	LL r,c;
	public:
		Martrix(LL raw, LL col) {
			r=raw; c=col;
			p=vector<LL>(r*c);
		}
		void setOriginal() {
			LL len=r*c;
			for (LL i=0; i<len; ++i) p[i]=0;
			for (LL i=0; i<r; ++i) {
				Ele(i,i)=1;
			}
		}
		LL getRaw() {
			return r;
		}
		LL getColumn() {
			return c;
		}
		void setEle(LL a[]) {
			LL len=r*c;
			for (int i=0; i<len; ++i) p[i]=a[i];
		}
		LL& Ele(int raw, int col) {
			return p[raw*r+col];
		}
		void print() {
			for (int i=0; i<r; ++i) {
				for (int j=0; j<c; ++j) {
					cout<<Ele(i,j)<<" ";
				}
				cout<<endl;
			}
		}
};
Martrix operator*(Martrix a, Martrix b) {
	LL len=a.getRaw();
	Martrix mar=Martrix(len, len);
	for (int i=0; i<len; ++i) {
		for (int j=0; j<len; ++j) {
			LL t=0;
			for (int k=0; k<len; ++k) {
				t=(t+a.Ele(i, k)*b.Ele(k, j)%MOD)%MOD;
			}
			mar.Ele(i,j)=t;
		}
	}
	return mar;
}
Martrix POW(LL k) {
	Martrix tmp(7,7);
	LL p[]={1,2,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,4,6,4,1,0,0,0,1,3,3,1,0,0,0,0,1,2,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1};
	tmp.setEle(p);
	Martrix res(7,7);
	res.setOriginal();
	while (k) {
		if (k&1) {
			res=(res*tmp);
		}
		tmp=(tmp*tmp);
		k=k>>1;
	}
	return res;
}
int main() {
	int T;
	cin>>T;
	LL n,a1,a2;
	LL t[]={0,0,81,27,9,3,1};
	while (T--) {
		cin>>n>>a1>>a2;
//		a1=a1%MOD;
//		a2=a2%MOD;
		if (n==1) cout<<a1<<endl;
		else if (n==2) cout<<a2<<endl;
		else {
			Martrix m=POW(n-2);
			LL res=0;
			t[0]=a2, t[1]=a1;
			for (int i=0; i<7; ++i) {
				res=(res+m.Ele(0,i)*t[i]%MOD)%MOD;
			}
			if (res<0) res+=MOD;
			cout<<res<<endl;
		}
	}
	return 0;
}
